#include "KMPStringMatch.h"

KMPStringMatch::KMPStringMatch(char *masterStr, char *modeStr)
{
	this->masterStr=masterStr;
	this->modeStr=modeStr;
}

KMPStringMatch::~KMPStringMatch()
{
}

void KMPStringMatch::getNextValue()
{
	int i=0, k=-1;
	const int modeStrLen=strlen(this->modeStr);
	this->next=new int[modeStrLen];
	this->next[0]=-1;

	while(i<modeStrLen-1)
	{
		while(k>=0 && this->modeStr[i]!=this->masterStr[k]) k=this->next[k];
		i++;
		k++;
		if(this->modeStr[i]==this->modeStr[k]) this->next[i]=this->next[k];
		else
			this->next[i]=k;
	}

	for(i=0;i<modeStrLen;i++)
		cout<<"next["<<i<<"]="<<this->next[i]<<endl;
}

int KMPStringMatch::doMatch()
{
	int i=0, j=0;
	int masterStrLen=strlen(this->masterStr);
	int modeStrLen=strlen(this->modeStr);

	getNextValue();

	while(i<modeStrLen && j<masterStrLen)
	{
		if(i==-1 || this->masterStr[j]==this->modeStr[i])
		{
			i++;
			j++;
		}else
		{
			i=next[i];
		}
	}

	if(i>=modeStrLen) return j-modeStrLen+1;
	else
		return 0;
}

int KMPStringMatch::run()
{
	return doMatch();
}

char* KMPStringMatch::getMasterStr()
{
	return this->masterStr;
}

char* KMPStringMatch::getModeStr()
{
	return this->modeStr;
}

void KMPStringMatch::setMasterStr(char * masterStr)
{
	this->masterStr=masterStr;
}

void KMPStringMatch::setModeStr(char *modeStr)
{
	this->modeStr=modeStr;
}

